package com.yiguang.algorithm.other;

import java.util.ArrayList;
import java.util.List;

import com.alibaba.fastjson.JSON;

/**
 * 滑动窗口
 * 239. 滑动窗口最大值
 * 
 */
public class SlidingWindow {
	
	public static void main(String[] args) {
		System.out.println(JSON.toJSONString(maxSlidingWindow2(new int[]{1,3,-1,-3,5,3,6,7}, 3)));
	}
	
	/**
	 * 239. 滑动窗口最大值
	 * 暴力法
	 */
	public static int[] maxSlidingWindow1(int[] nums, int k) {
		int[] result = new int[nums.length-k+1];
		for(int i=0; i<=nums.length-k; i++) {
			int max = nums[i];
			for(int j=i+1; j<i+k; j++) {
				if(nums[j]>max) {
					max = nums[j];
				}
			}
			result[i]=max;
		}
		return result;

    }
	
	/**
	 * 239. 滑动窗口最大值
	 * 优化：暂未
	 */
	public static int[] maxSlidingWindow2(int[] nums, int k) {
		int[] result = new int[nums.length-k+1];
		if(k==1) {
			return nums;
		}
		for(int i=0; i<=nums.length-k; i++) {
			if(i==0) {
				int max = nums[i];
				for(int j=i+1; j<i+k; j++) {
					if(nums[j]>max) {
						max = nums[j];
					}
				}
				result[i]=max;
			}else {
				result[i]=Math.max(result[i-1], nums[i+k-1]);
			}
		}
		return result;

    }
	
}
